Set-up

All of the tools that are strictly necessary for clustering are available in base R. For full flexibility, however, the ggdendro, protoclust, and heatmaply packages are recommended. If you want to explore further possibilities, look at the cluster package.

library(tidyverse)
โ”€โ”€ Attaching packages โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ tidyverse 1.2.1 โ”€โ”€
โœ” ggplot2 3.1.0       โœ” purrr   0.3.2  
โœ” tibble  2.1.1       โœ” dplyr   0.8.0.1
โœ” tidyr   0.8.3       โœ” stringr 1.4.0  
โœ” readr   1.3.1       โœ” forcats 0.4.0  
โ”€โ”€ Conflicts โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ tidyverse_conflicts() โ”€โ”€
โœ– dplyr::filter() masks stats::filter()
โœ– dplyr::lag()    masks stats::lag()
library(tidymodels)
โ”€โ”€ Attaching packages โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ tidymodels 0.0.2 โ”€โ”€
โœ” broom     0.5.1     โœ” recipes   0.1.4
โœ” dials     0.0.2     โœ” rsample   0.0.4
โœ” infer     0.4.0     โœ” yardstick 0.0.3
โœ” parsnip   0.0.1     
โ”€โ”€ Conflicts โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€ tidymodels_conflicts() โ”€โ”€
โœ– scales::discard() masks purrr::discard()
โœ– dplyr::filter()   masks stats::filter()
โœ– recipes::fixed()  masks stringr::fixed()
โœ– dplyr::lag()      masks stats::lag()
โœ– yardstick::spec() masks readr::spec()
โœ– recipes::step()   masks stats::step()
library(ggdendro)
library(protoclust)
library(heatmaply)
Loading required package: plotly

Attaching package: โ€˜plotlyโ€™

The following object is masked from โ€˜package:ggplot2โ€™:

    last_plot

The following object is masked from โ€˜package:statsโ€™:

    filter

The following object is masked from โ€˜package:graphicsโ€™:

    layout

Loading required package: viridis
Loading required package: viridisLite

Attaching package: โ€˜viridisโ€™

The following object is masked from โ€˜package:scalesโ€™:

    viridis_pal


======================
Welcome to heatmaply version 0.15.2

Type citation('heatmaply') for how to cite the package.
Type ?heatmaply for the main documentation.

The github page is: https://github.com/talgalili/heatmaply/
Please submit your suggestions and bug-reports at: https://github.com/talgalili/heatmaply/issues
Or contact: <tal.galili@gmail.com>
======================
library(spotifyr)
library(compmus)

Attaching package: โ€˜compmusโ€™

The following object is masked from โ€˜package:spotifyrโ€™:

    get_playlist_audio_features
source('spotify.R')

Clustering

The Bibliothรจque nationale de France (BnF) makes a large portion of its music collection available on Spotify, including an eclectic collection of curated playlists. The defining musical characteristics of these playlists are sometimes unclear: for example, they have a Halloween playlist. Perhaps clustering can help us organise and describe what kinds of musical selections make it into the BnFโ€™s playlist.

We begin by loading the playlist and summarising the pitch and timbre features, just like last week. Note that, also like last week, we use compmus_c_transpose to transpose the chroma features so that โ€“ depending on the accuracy of Spotifyโ€™s key estimation โ€“ we can interpret them as if every piece were in C major or C minor. Although this example includes no delta features, try adding them yourself if you are feeling comfortable with R!

halloween <- 
    get_playlist_audio_features('bnfcollection', '1vsoLSK3ArkpaIHmUaF02C') %>% 
    add_audio_analysis %>% 
    mutate(
        segments = 
            map2(segments, key, compmus_c_transpose)) %>% 
    mutate(
        segments =
            map(
                segments,
                mutate,
                delta_timbre = map2(timbre, lag(timbre), `-`))) %>% 
    mutate(
        pitches = 
            map(segments, 
                compmus_summarise, pitches, 
                method = 'mean', norm = 'manhattan'),
        timbre =
            map(
                segments,
                compmus_summarise, timbre,
                method = 'mean'),
        delta_timbre =
            map(
                segments,
                compmus_summarise, delta_timbre,
                method = 'mean')) %>% 
    mutate(pitches = map(pitches, compmus_normalise, 'clr')) %>% 
    mutate_at(vars(pitches, timbre, delta_timbre), map, bind_rows) %>% 
    unnest(pitches, timbre, delta_timbre)

Pre-processing

Remember that in the tidyverse approach, we can preprocess data with a recipe. In this case, instead of a label that we want to predict, we start with a label that will make the cluster plots readable. For most projects, the track name will be the best choice (although feel free to experiment with others). The code below uses str_trunc to clip the track name to a maximum of 20 characters, again in order to improve readability. The other change from last week is column_to_rownames, which is necessary for the plot labels to appear correctly.

Last week we also discussed that although standardising variables with step_center to make the mean 0 and step_scale to make the standard deviation 1 is the most common approach, sometimes step_range is a better alternative, which squashes or stretches every features so that it ranges from 0 to 1. For most classification algorithms, the difference is small; for clustering, the differences can be more noticable. Itโ€™s wise to try both.

halloween_juice <- 
    recipe(track_name ~
               danceability +
               energy +
               loudness +
               speechiness +
               acousticness +
               instrumentalness +
               liveness +
               valence +
               tempo +
               duration_ms +
               C + `C#|Db` + D + `D#|Eb` +
               E + `F` + `F#|Gb` + G +
               `G#|Ab` + A + `A#|Bb` + B +
               c01 + c02 + c03 + c04 + c05 + c06 +
               c07 + c08 + c09 + c10 + c11 + c12,
           data = halloween) %>% 
    step_center(all_predictors()) %>%
    step_scale(all_predictors()) %>%
    # step_range(all_predictors()) %>% 
    prep(halloween %>% mutate(track_name = str_trunc(track_name, 20))) %>% 
    juice %>% 
    column_to_rownames('track_name')

Computing distances

When using step_center and step_scale, then the Euclidean distance is usual. When using step_range, then the Manhattan distance is also a good choice: this combination is known as Gowerโ€™s distance and has a long history in clustering.

halloween_dist <- dist(halloween_juice, method = 'euclidean')

Hierarchical clustering

As you learned in your DataCamp exercises this week, there are three primary types of linkage: single, average, and complete. Usually average or complete give the best results. We can use the ggendrogram function to make a more standardised plot of the results.

hclust(halloween_dist, method = 'single') %>% dendro_data %>% ggdendrogram

A more recent โ€“ and often superior โ€“ linkage function is minimax linkage, available in the protoclust package. It is more akin to \(k\)-means: at each step, it chooses an ideal centroid for every cluster such that the maximum distance between centroids and all members of their respective clusters is as small as possible.

protoclust(halloween_dist) %>% dendro_data %>% ggdendrogram

Try all four of these linkages. Which one looks the best? Which one sounds the best (when you listen to the tracks on Spotify)? Can you guess which features are separating the clusters?

k-Means

Unlike hierarchical clustering, k-means clustering returns a different results every time. Nonetheless, it can be a useful reality check on the stability of the clusters from hierarchical clustering.

kmeans(halloween_juice, 4)
K-means clustering with 4 clusters of sizes 5, 7, 2, 6

Cluster means:
  danceability      energy   loudness speechiness acousticness instrumentalness    liveness    valence       tempo
1   0.64836983 -0.49710006  0.1245002  0.05224442    0.3870865     -0.367575835  0.62657491  0.2517858 -0.57764542
2  -1.20286793 -0.65481004 -0.8180242 -0.69484670    0.1960202     -0.002641033  0.08514692 -1.0319293 -0.13884228
3   0.09605479  0.07213439  0.5262965 -0.48145689    0.1384264      1.105519968  0.23473711  0.1471131 -0.02038562
4   0.83101946  1.15415030  0.6751792  0.92760310   -0.5974045     -0.059112255 -0.69972953  0.9450583  0.65014905
  duration_ms           C       C#|Db          D      D#|Eb          E          F      F#|Gb           G         G#|Ab
1 -0.07050269 -0.34809410  0.50342957 -0.4354586 -0.4435755 -1.0830882 -0.6567164  0.4805615  0.47929858  1.0426814710
2  0.36331256  0.03424285  0.12208631 -0.2036450  0.6233577  0.4252545  0.3213209 -0.6423839 -0.09781781  0.0001152723
3 -0.12646175  0.44130883 -1.77309313  1.3525471 -0.5766835  1.7594651 -0.5345336 -0.4481507  0.17806751 -2.0105648218
4 -0.32295850  0.10302548  0.02907237  0.1496190 -0.1653766 -0.1800450  0.3505671  0.4983636 -0.34465054 -0.1988474363
           A       A#|Bb          B        c01        c02        c03         c04        c05        c06          c07
1  0.3224897  0.78538950 -0.5982347 -0.6921753 -0.5563510 -0.5489469 -0.06467015  0.2282925  0.8266389 -0.164543931
2 -0.3356205  0.03918216 -0.3162802 -0.2106414 -0.2500977  0.3978360 -0.81726256  0.1383504 -0.8499680 -0.001680086
3  1.2442431 -1.91137400  1.8355507  0.9626355  1.2067481  1.7439574  1.40708521  0.5926782  0.1993832 -0.998983423
4 -0.2919318 -0.06307911  0.2556722  0.5016825  0.3531571 -0.5880053  0.53833638 -0.5492119  0.2363025  0.472074517
         c08        c09        c10        c11        c12
1  0.3382651  0.8217280  0.4590651 -0.9741404 -0.2838794
2  0.1770037  0.4068887 -0.6793797  0.9025014  0.6023293
3 -1.4265712 -0.9808208 -0.4151848  0.5479418 -0.2223407
4 -0.0128682 -0.8325366  0.5484503 -0.4237820 -0.3920377

Clustering vector:
I Put a Spell on You      Close Your Eyes           Evil Woman         Time to Kill       Evil Bad Woman 
                   4                    2                    4                    1                    1 
The Princess of Evil      'Round Midnight Tana's Theme - Fr...           Evil Blues  Someone Is Watching 
                   2                    2                    3                    1                    2 
Violin Sonata in ...         Cannibal Pot            Red Devil You're Not Living...         Little Demon 
                   3                    4                    4                    2                    4 
Devil at 4 O'Cloc...       Old Devil Moon  Up Jumped the Devil Beetween the Devi...          Devil Woman 
                   2                    4                    1                    1                    2 

Within cluster sum of squares by cluster:
[1] 104.86406 139.55752  29.47158 127.08693
 (between_SS / total_SS =  37.9 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss" "betweenss"    "size"        
[8] "iter"         "ifault"

Heatmaps

Especially for storyboards, it can be helpful to visualise hierarchical clusterings along with heatmaps of feature values. We can do that with heatmaply. Although the interactive heatmaps are flashly, think carefully when deciding whether this representation is more helpful for your storyboard than the simpler dendrograms above.

grDevices::dev.size("px")
[1] 525.0000 324.4747
heatmaply(
    halloween_juice,
    hclustfun = hclust,
    # hclustfun = protoclust,
    # Comment out the hclust_method line when using protoclust.
    hclust_method = 'average',
    dist_method = 'euclidean')

Which features seem to be the most and least useful for the clustering? What happens if you re-run this notebook using only the best features?

LS0tCnRpdGxlOiAiV2VlayAxMiDCtyBTaW1pbGFyaXR5IGFuZCBDbHVzdGVyaW5nIgphdXRob3I6ICJKb2huIEFzaGxleSBCdXJnb3luZSIKZGF0ZTogIjIwIE1hcmNoIDIwMTkiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdGhlbWU6IGZsYXRseQotLS0KCiMjIFNldC11cAoKQWxsIG9mIHRoZSB0b29scyB0aGF0IGFyZSBzdHJpY3RseSBuZWNlc3NhcnkgZm9yIGNsdXN0ZXJpbmcgYXJlIGF2YWlsYWJsZSBpbiBiYXNlIFIuIEZvciBmdWxsIGZsZXhpYmlsaXR5LCBob3dldmVyLCB0aGUgYGdnZGVuZHJvYCwgYHByb3RvY2x1c3RgLCBhbmQgYGhlYXRtYXBseWAgcGFja2FnZXMgYXJlIHJlY29tbWVuZGVkLiBJZiB5b3Ugd2FudCB0byBleHBsb3JlIGZ1cnRoZXIgcG9zc2liaWxpdGllcywgbG9vayBhdCB0aGUgYGNsdXN0ZXJgIHBhY2thZ2UuCgpgYGB7cn0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkodGlkeW1vZGVscykKbGlicmFyeShnZ2RlbmRybykKbGlicmFyeShwcm90b2NsdXN0KQpsaWJyYXJ5KGhlYXRtYXBseSkKbGlicmFyeShzcG90aWZ5cikKbGlicmFyeShjb21wbXVzKQpzb3VyY2UoJ3Nwb3RpZnkuUicpCmBgYAoKIyMgQ2x1c3RlcmluZwoKVGhlIEJpYmxpb3Row6hxdWUgbmF0aW9uYWxlIGRlIEZyYW5jZSAoQm5GKSBtYWtlcyBhIGxhcmdlIHBvcnRpb24gb2YgaXRzIFttdXNpYyBjb2xsZWN0aW9uXShodHRwczovL2dhbGxpY2EuYm5mLmZyL2h0bWwvdW5kL2JuZi1jb2xsZWN0aW9uLXNvbm9yZSkgYXZhaWxhYmxlIG9uIFNwb3RpZnksIGluY2x1ZGluZyBhbiBlY2xlY3RpYyBjb2xsZWN0aW9uIG9mIGN1cmF0ZWQgcGxheWxpc3RzLiBUaGUgZGVmaW5pbmcgbXVzaWNhbCBjaGFyYWN0ZXJpc3RpY3Mgb2YgdGhlc2UgcGxheWxpc3RzIGFyZSBzb21ldGltZXMgdW5jbGVhcjogZm9yIGV4YW1wbGUsIHRoZXkgaGF2ZSBhIEhhbGxvd2VlbiBwbGF5bGlzdC4gUGVyaGFwcyBjbHVzdGVyaW5nIGNhbiBoZWxwIHVzIG9yZ2FuaXNlIGFuZCBkZXNjcmliZSB3aGF0IGtpbmRzIG9mIG11c2ljYWwgc2VsZWN0aW9ucyBtYWtlIGl0IGludG8gdGhlIEJuRidzIHBsYXlsaXN0LgoKV2UgYmVnaW4gYnkgbG9hZGluZyB0aGUgcGxheWxpc3QgYW5kIHN1bW1hcmlzaW5nIHRoZSBwaXRjaCBhbmQgdGltYnJlIGZlYXR1cmVzLCBqdXN0IGxpa2UgbGFzdCB3ZWVrLiBOb3RlIHRoYXQsIGFsc28gbGlrZSBsYXN0IHdlZWssIHdlIHVzZSBgY29tcG11c19jX3RyYW5zcG9zZWAgdG8gdHJhbnNwb3NlIHRoZSBjaHJvbWEgZmVhdHVyZXMgc28gdGhhdCAtLSBkZXBlbmRpbmcgb24gdGhlIGFjY3VyYWN5IG9mIFNwb3RpZnkncyBrZXkgZXN0aW1hdGlvbiAtLSB3ZSBjYW4gaW50ZXJwcmV0IHRoZW0gYXMgaWYgZXZlcnkgcGllY2Ugd2VyZSBpbiBDIG1ham9yIG9yIEMgbWlub3IuIEFsdGhvdWdoIHRoaXMgZXhhbXBsZSBpbmNsdWRlcyBubyBkZWx0YSBmZWF0dXJlcywgdHJ5IGFkZGluZyB0aGVtIHlvdXJzZWxmIGlmIHlvdSBhcmUgZmVlbGluZyBjb21mb3J0YWJsZSB3aXRoIFIhCgpgYGB7cn0KaGFsbG93ZWVuIDwtIAogICAgZ2V0X3BsYXlsaXN0X2F1ZGlvX2ZlYXR1cmVzKCdibmZjb2xsZWN0aW9uJywgJzF2c29MU0szQXJrcGFJSG1VYUYwMkMnKSAlPiUgCiAgICBhZGRfYXVkaW9fYW5hbHlzaXMgJT4lIAogICAgbXV0YXRlKAogICAgICAgIHNlZ21lbnRzID0gCiAgICAgICAgICAgIG1hcDIoc2VnbWVudHMsIGtleSwgY29tcG11c19jX3RyYW5zcG9zZSkpICU+JSAKICAgIG11dGF0ZSgKICAgICAgICBwaXRjaGVzID0gCiAgICAgICAgICAgIG1hcChzZWdtZW50cywgCiAgICAgICAgICAgICAgICBjb21wbXVzX3N1bW1hcmlzZSwgcGl0Y2hlcywgCiAgICAgICAgICAgICAgICBtZXRob2QgPSAnbWVhbicsIG5vcm0gPSAnbWFuaGF0dGFuJyksCiAgICAgICAgdGltYnJlID0KICAgICAgICAgICAgbWFwKAogICAgICAgICAgICAgICAgc2VnbWVudHMsCiAgICAgICAgICAgICAgICBjb21wbXVzX3N1bW1hcmlzZSwgdGltYnJlLAogICAgICAgICAgICAgICAgbWV0aG9kID0gJ21lYW4nKSkgJT4lIAogICAgbXV0YXRlKHBpdGNoZXMgPSBtYXAocGl0Y2hlcywgY29tcG11c19ub3JtYWxpc2UsICdjbHInKSkgJT4lIAogICAgbXV0YXRlX2F0KHZhcnMocGl0Y2hlcywgdGltYnJlKSwgbWFwLCBiaW5kX3Jvd3MpICU+JSAKICAgIHVubmVzdChwaXRjaGVzLCB0aW1icmUpCmBgYAoKIyMjIFByZS1wcm9jZXNzaW5nCgpSZW1lbWJlciB0aGF0IGluIHRoZSBgdGlkeXZlcnNlYCBhcHByb2FjaCwgd2UgY2FuIHByZXByb2Nlc3MgZGF0YSB3aXRoIGEgYHJlY2lwZWAuIEluIHRoaXMgY2FzZSwgaW5zdGVhZCBvZiBhIGxhYmVsIHRoYXQgd2Ugd2FudCB0byBwcmVkaWN0LCB3ZSBzdGFydCB3aXRoIGEgbGFiZWwgdGhhdCB3aWxsIG1ha2UgdGhlIGNsdXN0ZXIgcGxvdHMgcmVhZGFibGUuIEZvciBtb3N0IHByb2plY3RzLCB0aGUgdHJhY2sgbmFtZSB3aWxsIGJlIHRoZSBiZXN0IGNob2ljZSAoYWx0aG91Z2ggZmVlbCBmcmVlIHRvIGV4cGVyaW1lbnQgd2l0aCBvdGhlcnMpLiBUaGUgY29kZSBiZWxvdyB1c2VzIGBzdHJfdHJ1bmNgIHRvIGNsaXAgdGhlIHRyYWNrIG5hbWUgdG8gYSBtYXhpbXVtIG9mIDIwIGNoYXJhY3RlcnMsIGFnYWluIGluIG9yZGVyIHRvIGltcHJvdmUgcmVhZGFiaWxpdHkuIFRoZSBvdGhlciBjaGFuZ2UgZnJvbSBsYXN0IHdlZWsgaXMgYGNvbHVtbl90b19yb3duYW1lc2AsIHdoaWNoIGlzIG5lY2Vzc2FyeSBmb3IgdGhlIHBsb3QgbGFiZWxzIHRvIGFwcGVhciBjb3JyZWN0bHkuCgpMYXN0IHdlZWsgd2UgYWxzbyBkaXNjdXNzZWQgdGhhdCBhbHRob3VnaCBzdGFuZGFyZGlzaW5nIHZhcmlhYmxlcyB3aXRoIGBzdGVwX2NlbnRlcmAgdG8gbWFrZSB0aGUgbWVhbiAwIGFuZCBgc3RlcF9zY2FsZWAgdG8gbWFrZSB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIDEgaXMgdGhlIG1vc3QgY29tbW9uIGFwcHJvYWNoLCBzb21ldGltZXMgYHN0ZXBfcmFuZ2VgIGlzIGEgYmV0dGVyIGFsdGVybmF0aXZlLCB3aGljaCBzcXVhc2hlcyBvciBzdHJldGNoZXMgZXZlcnkgZmVhdHVyZXMgc28gdGhhdCBpdCByYW5nZXMgZnJvbSAwIHRvIDEuIEZvciBtb3N0IGNsYXNzaWZpY2F0aW9uIGFsZ29yaXRobXMsIHRoZSBkaWZmZXJlbmNlIGlzIHNtYWxsOyBmb3IgY2x1c3RlcmluZywgdGhlIGRpZmZlcmVuY2VzIGNhbiBiZSBtb3JlIG5vdGljYWJsZS4gSXQncyB3aXNlIHRvIHRyeSBib3RoLgoKYGBge3J9CmhhbGxvd2Vlbl9qdWljZSA8LSAKICAgIHJlY2lwZSh0cmFja19uYW1lIH4KICAgICAgICAgICAgICAgZGFuY2VhYmlsaXR5ICsKICAgICAgICAgICAgICAgZW5lcmd5ICsKICAgICAgICAgICAgICAgbG91ZG5lc3MgKwogICAgICAgICAgICAgICBzcGVlY2hpbmVzcyArCiAgICAgICAgICAgICAgIGFjb3VzdGljbmVzcyArCiAgICAgICAgICAgICAgIGluc3RydW1lbnRhbG5lc3MgKwogICAgICAgICAgICAgICBsaXZlbmVzcyArCiAgICAgICAgICAgICAgIHZhbGVuY2UgKwogICAgICAgICAgICAgICB0ZW1wbyArCiAgICAgICAgICAgICAgIGR1cmF0aW9uX21zICsKICAgICAgICAgICAgICAgQyArIGBDI3xEYmAgKyBEICsgYEQjfEViYCArCiAgICAgICAgICAgICAgIEUgKyBgRmAgKyBgRiN8R2JgICsgRyArCiAgICAgICAgICAgICAgIGBHI3xBYmAgKyBBICsgYEEjfEJiYCArIEIgKwogICAgICAgICAgICAgICBjMDEgKyBjMDIgKyBjMDMgKyBjMDQgKyBjMDUgKyBjMDYgKwogICAgICAgICAgICAgICBjMDcgKyBjMDggKyBjMDkgKyBjMTAgKyBjMTEgKyBjMTIsCiAgICAgICAgICAgZGF0YSA9IGhhbGxvd2VlbikgJT4lIAogICAgc3RlcF9jZW50ZXIoYWxsX3ByZWRpY3RvcnMoKSkgJT4lCiAgICBzdGVwX3NjYWxlKGFsbF9wcmVkaWN0b3JzKCkpICU+JQogICAgIyBzdGVwX3JhbmdlKGFsbF9wcmVkaWN0b3JzKCkpICU+JSAKICAgIHByZXAoaGFsbG93ZWVuICU+JSBtdXRhdGUodHJhY2tfbmFtZSA9IHN0cl90cnVuYyh0cmFja19uYW1lLCAyMCkpKSAlPiUgCiAgICBqdWljZSAlPiUgCiAgICBjb2x1bW5fdG9fcm93bmFtZXMoJ3RyYWNrX25hbWUnKQpgYGAKCiMjIyBDb21wdXRpbmcgZGlzdGFuY2VzCgpXaGVuIHVzaW5nIGBzdGVwX2NlbnRlcmAgYW5kIGBzdGVwX3NjYWxlYCwgdGhlbiB0aGUgRXVjbGlkZWFuIGRpc3RhbmNlIGlzIHVzdWFsLiBXaGVuIHVzaW5nIGBzdGVwX3JhbmdlYCwgdGhlbiB0aGUgTWFuaGF0dGFuIGRpc3RhbmNlIGlzIGFsc28gYSBnb29kIGNob2ljZTogdGhpcyBjb21iaW5hdGlvbiBpcyBrbm93biBhcyAqR293ZXIncyBkaXN0YW5jZSogYW5kIGhhcyBhIGxvbmcgaGlzdG9yeSBpbiBjbHVzdGVyaW5nLgoKYGBge3J9CmhhbGxvd2Vlbl9kaXN0IDwtIGRpc3QoaGFsbG93ZWVuX2p1aWNlLCBtZXRob2QgPSAnZXVjbGlkZWFuJykKYGBgCgojIyMgSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcKCkFzIHlvdSBsZWFybmVkIGluIHlvdXIgRGF0YUNhbXAgZXhlcmNpc2VzIHRoaXMgd2VlaywgdGhlcmUgYXJlIHRocmVlIHByaW1hcnkgdHlwZXMgb2YgKmxpbmthZ2UqOiBzaW5nbGUsIGF2ZXJhZ2UsIGFuZCBjb21wbGV0ZS4gVXN1YWxseSBhdmVyYWdlIG9yIGNvbXBsZXRlIGdpdmUgdGhlIGJlc3QgcmVzdWx0cy4gV2UgY2FuIHVzZSB0aGUgYGdnZW5kcm9ncmFtYCBmdW5jdGlvbiB0byBtYWtlIGEgbW9yZSBzdGFuZGFyZGlzZWQgcGxvdCBvZiB0aGUgcmVzdWx0cy4KCmBgYHtyfQpoY2x1c3QoaGFsbG93ZWVuX2Rpc3QsIG1ldGhvZCA9ICdzaW5nbGUnKSAlPiUgZGVuZHJvX2RhdGEgJT4lIGdnZGVuZHJvZ3JhbQpgYGAKCkEgbW9yZSByZWNlbnQgLS0gYW5kIG9mdGVuIHN1cGVyaW9yIC0tIGxpbmthZ2UgZnVuY3Rpb24gaXMgKm1pbmltYXggbGlua2FnZSosIGF2YWlsYWJsZSBpbiB0aGUgYHByb3RvY2x1c3RgIHBhY2thZ2UuIEl0IGlzIG1vcmUgYWtpbiB0byAkayQtbWVhbnM6IGF0IGVhY2ggc3RlcCwgaXQgY2hvb3NlcyBhbiBpZGVhbCBjZW50cm9pZCBmb3IgZXZlcnkgY2x1c3RlciBzdWNoIHRoYXQgdGhlIG1heGltdW0gZGlzdGFuY2UgYmV0d2VlbiBjZW50cm9pZHMgYW5kIGFsbCBtZW1iZXJzIG9mIHRoZWlyIHJlc3BlY3RpdmUgY2x1c3RlcnMgaXMgYXMgc21hbGwgYXMgcG9zc2libGUuCgpgYGB7cn0KcHJvdG9jbHVzdChoYWxsb3dlZW5fZGlzdCkgJT4lIGRlbmRyb19kYXRhICU+JSBnZ2RlbmRyb2dyYW0KYGBgCgpUcnkgYWxsIGZvdXIgb2YgdGhlc2UgbGlua2FnZXMuIFdoaWNoIG9uZSBsb29rcyB0aGUgYmVzdD8gV2hpY2ggb25lICpzb3VuZHMqIHRoZSBiZXN0ICh3aGVuIHlvdSBsaXN0ZW4gdG8gdGhlIHRyYWNrcyBvbiBTcG90aWZ5KT8gQ2FuIHlvdSBndWVzcyB3aGljaCBmZWF0dXJlcyBhcmUgc2VwYXJhdGluZyB0aGUgY2x1c3RlcnM/IAoKIyMjICprKi1NZWFucwoKVW5saWtlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nLCAqayotbWVhbnMgY2x1c3RlcmluZyByZXR1cm5zIGEgZGlmZmVyZW50IHJlc3VsdHMgZXZlcnkgdGltZS4gTm9uZXRoZWxlc3MsIGl0IGNhbiBiZSBhIHVzZWZ1bCByZWFsaXR5IGNoZWNrIG9uIHRoZSBzdGFiaWxpdHkgb2YgdGhlIGNsdXN0ZXJzIGZyb20gaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcuCgpgYGB7cn0Ka21lYW5zKGhhbGxvd2Vlbl9qdWljZSwgNCkKYGBgCgojIyMgSGVhdG1hcHMKCkVzcGVjaWFsbHkgZm9yIHN0b3J5Ym9hcmRzLCBpdCBjYW4gYmUgaGVscGZ1bCB0byB2aXN1YWxpc2UgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmdzIGFsb25nIHdpdGggaGVhdG1hcHMgb2YgZmVhdHVyZSB2YWx1ZXMuIFdlIGNhbiBkbyB0aGF0IHdpdGggYGhlYXRtYXBseWAuIEFsdGhvdWdoIHRoZSBpbnRlcmFjdGl2ZSBoZWF0bWFwcyBhcmUgZmxhc2hseSwgdGhpbmsgY2FyZWZ1bGx5IHdoZW4gZGVjaWRpbmcgd2hldGhlciB0aGlzIHJlcHJlc2VudGF0aW9uIGlzIG1vcmUgaGVscGZ1bCBmb3IgeW91ciBzdG9yeWJvYXJkIHRoYW4gdGhlIHNpbXBsZXIgZGVuZHJvZ3JhbXMgYWJvdmUuIAoKYGBge3J9CmdyRGV2aWNlczo6ZGV2LnNpemUoInB4IikKaGVhdG1hcGx5KAogICAgaGFsbG93ZWVuX2p1aWNlLAogICAgaGNsdXN0ZnVuID0gaGNsdXN0LAogICAgIyBoY2x1c3RmdW4gPSBwcm90b2NsdXN0LAogICAgIyBDb21tZW50IG91dCB0aGUgaGNsdXN0X21ldGhvZCBsaW5lIHdoZW4gdXNpbmcgcHJvdG9jbHVzdC4KICAgIGhjbHVzdF9tZXRob2QgPSAnYXZlcmFnZScsCiAgICBkaXN0X21ldGhvZCA9ICdldWNsaWRlYW4nKQpgYGAKCldoaWNoIGZlYXR1cmVzIHNlZW0gdG8gYmUgdGhlIG1vc3QgYW5kIGxlYXN0IHVzZWZ1bCBmb3IgdGhlIGNsdXN0ZXJpbmc/IFdoYXQgaGFwcGVucyBpZiB5b3UgcmUtcnVuIHRoaXMgbm90ZWJvb2sgdXNpbmcgb25seSB0aGUgYmVzdCBmZWF0dXJlcz8K